home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 22 / Cream of the Crop 22.iso / program / snpd9611.zip / SKIPLIST.C < prev    next >
C/C++ Source or Header  |  1996-11-24  |  7KB  |  297 lines

  1. /* +++Date last modified: 16-Nov-1996 */
  2.  
  3. /* - skiplist.c --------------------------------------------------- *
  4. **
  5. ** Once upon a time Skiplist were invented by William Pugh at the
  6. ** University of Maryland (according to Bruce Schneier, DrDobbs,
  7. ** january 1994). They are an elegant alternative approach to balanced
  8. ** binary threes.
  9. **
  10. ** Unfortunately the implementation shown in that same article did
  11. ** not yield the expected results, so I decided to "roll my own"
  12. ** rather than looking for errors in somebody elses code.
  13. **
  14. ** The result (surprise?) looked remarkably like the original version,
  15. ** except that it worked with my compiler, that is, untill I turned on
  16. ** the optimizer! (Lattice 5.06.02)
  17. **
  18. ** I then started to tweak the code, changing while to do/while or
  19. ** variable++; to ++variable; in order to fool the optimizer into
  20. ** doing what I intended to be done. (All very esoteric ;)
  21. **
  22. ** I have since then tested with gcc (DecStation) which works, and
  23. ** also cc -O3 (DecStation) which now works (This last one one was
  24. ** a beast!!)
  25. **
  26. ** If your compiler/optimizer still cannot digest this,
  27. ** then please let me know,
  28. **
  29. ** else tweak this file to be useful in your own projects
  30. ** and (if you like?) send me a "postcard" :-)
  31. **
  32. ** 17.08.1996 // Jens M Andreasen <jens-and@dsv.su.se>
  33. **
  34. ** In a message of 20-Aug-1996, Jens M Andreasen wrote:
  35. **
  36. ** My skiplist.c listing is hereby explicitly given the status of freeware.
  37. ** Distribute as is with the following additions ...
  38. **
  39. ** ------------------------------------------------------------------------
  40. **
  41. ** Note that the integers used for key and value are assumed to be 32 bit.
  42. **
  43. ** Note also that the randomgenerator is a temporary hack. The original
  44. ** implementation has a better one. And do take a look at the alternative
  45. ** approches to DUPLICATEFOUND while you are at it:
  46. */
  47.  
  48. #include<limits.h>
  49. #include<stdlib.h>
  50. #include<stdio.h>
  51.  
  52. #define LEVELMAX 15
  53. #define keytype int
  54. #define valuetype int
  55. #define KEYMAX INT_MAX
  56.  
  57. typedef struct structnode node;
  58. typedef struct structnode{
  59.       int key;
  60.       int value;
  61.       node *next[1];
  62. } *pt_node;
  63.  
  64.  
  65. /* ---------------------------------------------------------------- */
  66.  
  67. #define New(type) malloc(sizeof (type))
  68. #define NewArray(type,x) malloc(sizeof(type) * (x))
  69. #define NewNode(randomlevel)\
  70.  malloc(sizeof(node) + (randomlevel) * sizeof(pt_node))
  71.  
  72. int insertnode(node **List, int key, int value);
  73. #define DUPLICATEFOUND /* return -1 */
  74.  
  75. int findnode(node **List, int key);
  76. #define INITVALUE 0
  77.  
  78. int deletenode(node **List, int key);
  79.  
  80. void findall(node **List);/* under construction */
  81.  
  82. node **newlist(void);
  83.  
  84. int main(void);
  85.  
  86.  
  87. /* ---------------------------------------------------------------- */
  88.  
  89.  
  90.  
  91. int insertnode(node **List, int key, int value)
  92. {
  93.       int r,level = LEVELMAX;
  94.       node *temp  = List[0], **bTrack[LEVELMAX+1];
  95.  
  96.       if (temp->key > key)
  97.       {
  98.             do
  99.                   bTrack[level] = List;
  100.             while (--level >= 0);
  101.       }
  102.       else
  103.       {
  104.             do
  105.             {
  106.                   while((temp = List[level]), (temp->key < key))
  107.                   {
  108.                         List = temp->next;
  109.                   }
  110.                   bTrack[level] = List;
  111.             } while (--level >= 0);
  112.  
  113.             if (temp->key == key)
  114.             {
  115.                   DUPLICATEFOUND;
  116.                   temp->value = value;
  117.                   return 0;
  118.             }
  119.       }
  120.  
  121.       r = rand(); /* not so random, but works for now ... */
  122.       level = 0;
  123.  
  124.       while (r & 0x4000)
  125.       {
  126.             r <<= 1;
  127.             ++level;
  128.       }
  129.  
  130.       temp = NewNode(level);
  131.       if (!temp)
  132.       {
  133.             printf(" Out of memory at key: %d",key);
  134.             exit(1);
  135.       }
  136.  
  137.       temp->value = value;
  138.       temp->key   = key;
  139.  
  140.       do{
  141.             temp->next[level] = bTrack[level][level];
  142.             bTrack[level][level] = temp;
  143.       } while (--level >= 0);
  144.  
  145.       return 1;
  146.  }
  147.  
  148. int findnode(node **List, int key)
  149. {
  150.       int  level = LEVELMAX;
  151.       node *temp = List[0];
  152.  
  153.       if (temp->key > key)
  154.             return INITVALUE;
  155.  
  156.       do
  157.       {
  158.             while(temp = List[level], (temp->key < key))
  159.             {
  160.                   List = temp->next;
  161.             }
  162.       } while (--level >= 0);
  163.  
  164.       if (temp->key == key)
  165.       {
  166.             return temp->value;
  167.       }
  168.       else  return INITVALUE;
  169.  }
  170.  
  171.  
  172.  
  173. int deletenode(node **List, int key)
  174. {
  175.       int level  = LEVELMAX;
  176.       node *temp = List[0], **bTrack[LEVELMAX + 1];
  177.  
  178.       if ((temp->key > key)||(KEYMAX == key))
  179.             return 0;
  180.  
  181.       do
  182.       {
  183.             while(bTrack[level] = List, temp = List[level], (temp->key < key))
  184.             {
  185.                   List=temp->next;
  186.             }
  187.  
  188.       } while (--level >= 0);
  189.  
  190.       if (temp->key == key)
  191.       {
  192.             level=0;
  193.             do
  194.             {
  195.                   bTrack[level][level] = temp->next[level];
  196.             } while (++level, bTrack[level][level]->key == key);
  197.  
  198.             free(temp);
  199.             return -1;
  200.       }
  201.       return 0;
  202.  }
  203.  
  204.  
  205.  
  206. void findall(node **List)                 /* just testing ... */
  207. {
  208.       while (List && List[0])
  209.       {
  210.             ++List[0]->value;
  211.             --List[0]->value;
  212.  
  213.             List = List[0]->next;
  214.       }
  215. }
  216.  
  217. node **newlist(void)
  218. {
  219.       int l = LEVELMAX;
  220.       node *NIL,
  221.  
  222.       **L = NewArray(pt_node, LEVELMAX + 1);
  223.  
  224.       NIL = NewNode(LEVELMAX);
  225.  
  226.       NIL->key   = KEYMAX;
  227.       NIL->value = INITVALUE;
  228.       do
  229.       {
  230.             NIL->next[l] = NULL;
  231.       } while (l--);
  232.  
  233.       l=LEVELMAX;
  234.       do
  235.       {
  236.             L[l] = NIL;
  237.       } while (l--);
  238.  
  239.       return L;
  240.  }
  241.  
  242.  
  243. /* ---------------------------------------------------------------- */
  244.  
  245.  
  246. int main(void)
  247. {
  248.       int i;
  249.       node **L;
  250.  
  251.       if (sizeof(int) < 4)
  252.       {
  253.             puts("This code must be compiled with 32-bit ints!");
  254.             return EXIT_FAILURE;
  255.       }
  256.  
  257.       L=newlist();
  258.  
  259.       puts(" DOWN");
  260.  
  261.       for(i = 100000; i >= 0; i -=2)
  262.             insertnode(L, i, i);
  263.  
  264.       puts(" UP");
  265.       for(i = 1; i < 100000; i += 2)
  266.             insertnode(L, i, i);
  267.  
  268.       deletenode(L, 40);
  269.  
  270.       puts(" FIND");
  271.       for(i = -2; i <= 100002; ++i)
  272.             findnode(L, i);
  273.  
  274.       puts(" FAST");
  275.       findall(L);
  276.  
  277.       puts("SAMPLES");
  278.       printf(" %d", findnode(L, -10));
  279.  
  280.       printf(" %d,", findnode(L, 0));
  281.       printf(" %d", findnode(L, 1));
  282.       printf(" %d", findnode(L, 2));
  283.       printf(" %d", findnode(L, 39));
  284.       printf(" %d", findnode(L, 40));
  285.       printf(" %d", findnode(L, 41));
  286.       printf(" %d", findnode(L, 42));
  287.       printf(" %d", findnode(L, 99999));
  288.       printf(" %d", findnode(L, 100000));
  289.  
  290.       printf(", %d", findnode(L, 100001));
  291.       printf(" %d", findnode(L, 100008));
  292.  
  293.       puts(" DONE");
  294.  
  295.       return EXIT_SUCCESS;
  296. }
  297.